\documentclass[12pt,a4paper,french]{article}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage{a4}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{framed}
\usepackage{dsfont}
\usepackage[amsmath,thmmarks,thref,framed]{ntheorem}
\usepackage[dvips]{graphics}
\usepackage{epsfig}
\usepackage{calc}
\usepackage{tabls}
\usepackage{slashbox}
\usepackage{times}
\usepackage{tabularx}
\usepackage{multicol}
\usepackage{textcomp}

\usepackage{pst-all}

\usepackage[a4paper]{geometry}

\input{symboles.sty}

\geometry{hmargin=1cm, vmargin=1.5cm}

\title{
Département d'informatique (décembre 09).\\
Partiel de mathématiques discrètes. Semestre 1}

\date{}

\begin{document}

\vspace{-5em}
\maketitle


\vspace{-5em}
\noindent Seule une fiche manuscrite de format A5 est autorisée.\\ 




\vspace{-3em}
\section{QCM}

Cette partie contient 60 affirmations. Vous aurez +1 à chaque valeur de vérité trouvée, -1 à chaque erreur (et 0 en absence de réponse). Les notes seront ajustées à l'intervalle $[0;20]$ (les notes négatives auront 0).

Q. 1. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite réflexive si, lorsque $x$ est en relation avec $y$, alors $y$ est en relation avec $x$. L'assertion proposée est vraie ou fausse ?

%Q. 2. La puissance du continu est la puissance de $\mathds{R}$.
%L'assertion proposée est vraie ou fausse ?

%Q. 80. 
Q. 2. Soit $t_1$ et $t_2$ deux termes exprimés dans une algèbre de Boole munie des opérateurs classiques +, . et $\overline{\begin{array}{l}~\end{array}}$.
Si $t_1 +  t_2 = 1$ alors $t_1 = 1 $ et $t_2$ a une valeur quelconque, et vice versa.
 L'assertion proposée est vraie ou fausse ?




Q. 3. Soit $\mathcal{R}$ une relation binaire. Pour tout $x$ de $E$, il existe au plus un $y$ de $F$ tel que $x \mathcal{R} y$.
L'assertion proposée est vraie ou fausse ?

Q. 4. Une application est une relation fonctionnelle telle que tout élément de l'ensemble de départ possède au moins une image.
L'assertion proposée est vraie ou fausse ?

Q. 5. Une application est une relation binaire. L'assertion proposée est vraie ou fausse ?

Q. 6. Étant donnée la relation $\mathcal{R}$ dans $C=\{1,2,3,4,5\}$ définie par les points figurant
dans le diagramme cartésien:
\begin{multicols}{2}
\begin{center}
\psset{xunit=0.5, yunit=0.5}
\begin{pspicture}(0,-0.5)(6,6)
%\psgrid
\psaxes*[linewidth=1.2pt,labels=all,ticks=all]{->}(0,0)(0,0)(6,6)
\savedata{\mydata}[
{{1,2},{1,4},{3,1},{3,4},{3,5},{5,1},{5,2},{5,4}}]
\listplot[plotstyle=dots,showpoints=true]{\mydata}
\end{pspicture}
\end{center}

Le domaine de $\mathcal{R}$ est-il $\{1,2,3,4,5\}$?
\end{multicols}

Q. 7. $\sqrt{} : \mathbb{R}^+ \longrightarrow \mathbb{R}$ est surjective.
L'assertion proposée est vraie ou fausse ?

Q. 8. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite transitive si $\forall x \in E, x \mathcal{R} x$. L'assertion proposée est vraie ou fausse ?

Q. 9. Les relations d'ordre sont les relations réflexive, symétrique et transitive. L'assertion proposée est vraie ou fausse ?

Q. 10. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite  réflexive lorsque, si $x$ est en relation avec $y$, et si $y$ l'est avec $z$, alors $x$ est en relation avec $z$. L'assertion proposée est vraie ou fausse ?

Q. 11. Soit $R$ la relation dans $A=\{1,2,3,4\}$ définie par
$R=\{(1,3),(1,4),(3,2),(3,3),(3,4),\}$.
A-t-on $R^{-1}=\{(1,3),(1,4),(3,2),(3,3),(3,4),(1,3),(1,4),(3,2),(3,3),(3,4),\}$?


Q. 12. Étant donnée la relation $\mathcal{R}$ dans $C=\{1,2,3,4,5\}$ définie par les points figurant
dans le diagramme cartésien:
\begin{multicols}{2}
\begin{center}
\psset{xunit=0.5, yunit=0.5}
\begin{pspicture}(0,-0.5)(6,6)
%\psgrid
\psaxes*[linewidth=1.2pt,labels=all,ticks=all]{->}(0,0)(0,0)(6,6)
\savedata{\mydata}[
{{1,2},{1,4},{3,1},{3,4},{3,5},{5,1},{5,2},{5,4}}]
\listplot[plotstyle=dots,showpoints=true]{\mydata}
\end{pspicture}
\end{center}

Le domaine de $\mathcal{R}$ est-il $\{1,3,5\}$?
\end{multicols}

Q. 13. Soit $\mathcal{R}$ une relation binaire. $\forall x, x \mathcal{R} x$.
L'assertion proposée est vraie ou fausse ?

%doublon 
%Q. 14. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite réflexive si, lorsque $x$ est en relation avec $y$, alors $y$ est en relation avec $x$. L'assertion proposée est vraie ou fausse ?
% Q.70.
Q. 14. Une application bijective est surjective. L'assertion proposée est vraie ou fausse ?




Q. 15. $|$ est une relation d'ordre dans $\mathds{Z}$.
L'assertion proposée est vraie ou fausse ?

Q. 16. $(\mathds{R},\leqslant)$ est un ensemble ordonné. L'assertion proposée est vraie ou fausse ?

Q. 17. Les relations d'ordre sont les relations symétrique, antisymétrique et transitive.
L'assertion proposée est vraie ou fausse ?

% doublon 
%Q. 18. Une application est une relation binaire.
%L'assertion proposée est vraie ou fausse ?
% Q. 64. 
Q. 18. $\sin : [0,\pi] \longrightarrow [-1,1]$ est surjective. L'assertion proposée est vraie ou fausse ?



Q. 19. $(\mathds{N},|)$ est un ensemble ordonné. L'assertion proposée est vraie ou fausse ?

Q. 20. $\sin : \mathbb{R} \longrightarrow [-1,1]$ est injective. L'assertion proposée est vraie ou fausse ?

Q. 21. $\mathcal{R} = \{ (x,y) \in \mathbb{R}^2, xy = 1 \}$ est une relation fonctionnelle.
L'assertion proposée est vraie ou fausse ?

Q. 22. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite antisymétrique si $\forall x \in E, (x,x) \in G$. L'assertion proposée est vraie ou fausse ?

Q. 23. 
Dans une algèbre de Boole munie des opérateurs classiques +, . et $\overline{\begin{array}{l}~\end{array}}$, on considère l'expression 
$E=\overline{a}(a+b)(a+c)(a+d)(a+e)$. La version la plus réduite de $E$ est $\overline{a}bcde$.
 L'assertion proposée est vraie ou fausse ?


Q. 24. $(\mathds{N}^*,|)$ est un ensemble ordonné.
L'assertion proposée est vraie ou fausse ?

Q. 25. Étant donnée la relation $\mathcal{R}$ dans $C=\{1,2,3,4,5\}$ définie par les points figurant
dans le diagramme cartésien:
\begin{multicols}{2}
\begin{center}
\psset{xunit=0.5, yunit=0.5}
\begin{pspicture}(0,-0.5)(6,6)
%\psgrid
\psaxes*[linewidth=1.2pt,labels=all,ticks=all]{->}(0,0)(0,0)(6,6)
\savedata{\mydata}[
{{1,2},{1,4},{3,1},{3,4},{3,5},{5,1},{5,2},{5,4}}]
\listplot[plotstyle=dots,showpoints=true]{\mydata}
\end{pspicture}
\end{center}

On propose les affirmations suivantes:
\begin{enumerate}
\item \label{item:af1} $1 \mathcal{R}4$;
\item \label{item:af2} $2 \mathcal{R}5$;
\item \label{item:af3} $3 \mathcal{R}1$;
\item \label{item:af4} $5 \mathcal{R}3$.
\end{enumerate}
 Toutes les relations sont-elles vraies?

\end{multicols}
Q. 26. 
Dans une algèbre de Boole munie des opérateurs classiques +, . et $\overline{\begin{array}{l}~\end{array}}$, on considère l'expression 
$E=\overline{a}(a+b)(a+c)(a+d)(a+e)$. La version la plus réduite de $E$ est 1.
 L'assertion proposée est vraie ou fausse ?


Q. 27. Étant donnée la relation $\mathcal{R}$ dans $C=\{1,2,3,4,5\}$ définie par les points figurant
dans le diagramme cartésien:
\begin{multicols}{2}
\begin{center}
\psset{xunit=0.5, yunit=0.5}
\begin{pspicture}(0,-0.5)(6,6)
%\psgrid
\psaxes*[linewidth=1.2pt,labels=all,ticks=all]{->}(0,0)(0,0)(6,6)
\savedata{\mydata}[
{{1,2},{1,4},{3,1},{3,4},{3,5},{5,1},{5,2},{5,4}}]
\listplot[plotstyle=dots,showpoints=true]{\mydata}
\end{pspicture}
\end{center}

On propose les affirmations suivantes:
\begin{enumerate}
\item \label{item:af1b} $1 \mathcal{R}4$;
\item \label{item:af2b} $2 \mathcal{R}5$;
\item \label{item:af3b} $3 \mathcal{R}1$;
\item \label{item:af4b} $5 \mathcal{R}3$.
\end{enumerate}
L'item \ref{item:af4b} est-il toujours faux?

\end{multicols}

Q. 28. $x \mathcal{R} y \Longleftrightarrow $ \og $x$ et $y$ ont le même reste dans une division par 2 \fg{} est une relation d'ordre sur les entiers strictement positifs. L'assertion proposée est vraie ou fausse ?

Q. 29. Une application de $E$ dans $F$ est telle que $\forall x \in E$, il existe un unique élément $y \in F$ en relation avec $x$. L'assertion proposée est vraie ou fausse ?

Q. 30. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite réflexive si $\forall x \in E, x \mathcal{R} x$. L'assertion proposée est vraie ou fausse ?

Q. 31. $\mathcal{R} = \{ (x,y) \in \mathbb{R}^2, y-x+2 = 0 \}$ est une relation binaire.
L'assertion proposée est vraie ou fausse ?

%Q. 32. $\mathds{C}$ a la puissance du continu.
%L'assertion proposée est vraie ou fausse ?\\ 
% Q. 79. 
% doublon
%Q. 32. $\sin : \mathbb{R} \longrightarrow [-1,1]$ est injective.
%L'assertion proposée est vraie ou fausse ?
Q. 32. Les applications bijectives sont les applications injectives et surjectives. L'assertion proposée est vraie ou fausse ?


Q. 33. Soit $\mathcal{R}$ une relation binaire. Le graphe de $\mathcal{R}$ est symétrique par rapport à la diagonale.
L'assertion proposée est vraie ou fausse ?

%Q. 34. La puissance du continu est la puissance de $\mathds{N}$.
%L'assertion proposée est vraie ou fausse ?

%Q. 78. 
Q. 34. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite réflexive si la diagonale de $E^2$ est incluse dans $G$. L'assertion proposée est vraie ou fausse ?


% doublon
%Q. 35. Les relations d'ordre sont les relations réflexive, symétrique et transitive.
%L'assertion proposée est vraie ou fausse ?
Q. 35.
$\subset$ est une relation d'ordre dans $\mathcal{P}(E)$.
 L'assertion proposée est vraie ou fausse ?



Q. 36. Une application injective est une application telle que tout élément de l'ensemble d'arrivée possède au plus un antécédent. L'assertion proposée est vraie ou fausse ?

Q. 37. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite transitive lorsque, si $x$ est en relation avec $y$, et si $y$ l'est avec $z$, alors $x$ est en relation avec $z$. L'assertion proposée est vraie ou fausse ?

Q. 38. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite transitive si la diagonale de $E^2$ est incluse dans $G$. L'assertion proposée est vraie ou fausse ?

Q. 39. Une application surjective est une application telle que tout élément de l'ensemble d'arrivée possède au moins un antécédent.
L'assertion proposée est vraie ou fausse ?

Q. 40. Étant donnée la relation $\mathcal{R}$ dans $C=\{1,2,3,4,5\}$ définie par les points figurant
dans le diagramme cartésien:
\begin{multicols}{2}
\begin{center}
\psset{xunit=0.5, yunit=0.5}
\begin{pspicture}(0,-0.5)(6,6)
%\psgrid
\psaxes*[linewidth=1.2pt,labels=all,ticks=all]{->}(0,0)(0,0)(6,6)
\savedata{\mydata}[
{{1,2},{1,4},{3,1},{3,4},{3,5},{5,1},{5,2},{5,4}}]
\listplot[plotstyle=dots,showpoints=true]{\mydata}
\end{pspicture}
\end{center}

Le domaine de $\mathcal{R}$ est-il
$\{1,3,5\} \times \{1,2,4,5\}$?

\end{multicols}
Q. 41. $\sin : \mathbb{R} \longrightarrow [-1,1]$ est surjective.
L'assertion proposée est vraie ou fausse ?

%Q. 42. $\mathds{Z}$ a la puissance du continu.
%L'assertion proposée est vraie ou fausse ?

%Q. 77. 
Q. 42. Une application de $F$ dans $E$ est telle que $\forall x \in F$, il existe un unique élément $y \in E$ en relation avec $x$.
L'assertion proposée est vraie ou fausse ?


Q. 43. Toute application injective est surjective.
L'assertion proposée est vraie ou fausse ?

Q. 44. On a défini une relation binaire $\mathcal{R}$ entre deux ensembles $E$ et $F$ lorsqu’on s'est donné une partie de $E \times F$.
L'assertion proposée est vraie ou fausse ?

%Q. 45. $\mathcal{P}\left(\mathds{R}\right)$ a la puissance du continu.
%L'assertion proposée est vraie ou fausse ?\\ 
%Q. 76. 
%doublon
%Q. 45. Soit $\mathcal{R}$ une relation binaire. $\forall x, x \mathcal{R} x$. L'assertion proposée est vraie ou fausse ?
% doublon
% Q. 45. $\sin : \mathbb{R} \longrightarrow [-1,1]$ est surjective. L'assertion proposée est vraie ou fausse ?
Q.45. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite transitive si, lorsque $x$ est en relation avec $y$, alors $y$ ne peut pas être en relation avec $x$ (sauf si $x=y$). L'assertion proposée est vraie ou fausse ?


Q. 46. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite transitive quand tout élément est en relation avec lui-même. L'assertion proposée est vraie ou fausse ?

Q. 47. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite transitive si, lorsque $x$ est en relation avec $y$, alors $y$ est en relation avec $x$. L'assertion proposée est vraie ou fausse ?

Q. 48. \og $x \mathcal{R} y$ si et seulement si $x+y$ est pair \fg{} est une relation d'ordre sur l'ensemble des entiers relatifs.
L'assertion proposée est vraie ou fausse ?

Q. 49. $\{ (x,y) \in \mathbb{R}^2, |y| = \sqrt{x} \}$ est une relation fonctionnelle.
L'assertion proposée est vraie ou fausse ?

%Q. 50. $\mathcal{P}\left(\mathds{N}\right)$ a la puissance du continu.
%L'assertion proposée est vraie ou fausse ?\\ 
%Q. 75. 

Q. 50. $\leqslant$ est une relation d'ordre dans $\mathds{R}$.
L'assertion proposée est vraie ou fausse ?

Q. 51. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite antisymétrique si $$\forall (x,y,z) \in E^3, (x,y) \in G \textrm{ et } (y,z) \in G \Longrightarrow (x,z) \in G$$. L'assertion proposée est vraie ou fausse ?

%Q. 52. $\mathds{D}$ a la puissance du continu.
%L'assertion proposée est vraie ou fausse ?\\ 
%Q. 74. 
Q. 52. Soit $R$ la relation dans $A=\{1,2,3,4\}$ définie par
$R=\{(1,3),(1,4),(3,2),(3,3),(3,4),\}$.
A-t-on  $R^{-1}=\{(3,1),(4,1),(2,3),(3,3),(4,3)\}$?


Q. 53. $(\mathds{Z},|)$ est un ensemble ordonné. L'assertion proposée est vraie ou fausse ?

Q. 54. 
On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif, 
le . est le symbole du ET logique et $\overline{\begin{array}{l}~\end{array}}$ est la négation logique.
L'expression $\overline{a} + \overline{b} + c + d $ vaut 1 si et seulement $c.d$ vaut 1. L'assertion proposée est vraie ou fausse ?

Q. 55. $|$ est une relation d'ordre dans $\mathds{N}^*$.
L'assertion proposée est vraie ou fausse ?

Q. 56. 
On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif, 
le . est le symbole du ET logique et $\overline{\begin{array}{l}~\end{array}}$ est la négation logique.
L'égalité $a+b+c+d=0$ est établie si et seulement si $a= b= c= d = 0$. L'assertion  proposée est vraie ou fausse ?

Q. 57. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite transitive si $$\forall (x,y,z) \in E^3, x \mathcal{R} y \textrm{ et } y \mathcal{R} z \Longrightarrow x \mathcal{R} z$$. L'assertion proposée est vraie ou fausse ?

Q. 58. 
Étant données les fonctions $f:A \rightarrow B$,
$g:B \rightarrow C$ et
$h:C \rightarrow D$ définies par le diagramme suivants
\begin{multicols}{2}
\begin{center}
\pspicture*(-1,-1)(7,5.4)
\scalebox{1}{
\cnodeput*(0,4){a}{a}
\cnodeput*(0,3){b}{b}
\cnodeput*(0,2){c}{c}
\cnodeput*(2,4){1}{1}
\cnodeput*(2,3){2}{2}
\cnodeput*(2,2){3}{3}
\cnodeput*(4,4){x}{x}
\cnodeput*(4,3){y}{y}
\cnodeput*(4,2){z}{z}
\cnodeput*(4,1){w}{w}
\cnodeput*(6,4){4}{4}
\cnodeput*(6,3){5}{5}
\cnodeput*(6,2){6}{6}

\rput(-0.2,5.2){$A$}
\rput(1.8,5.2){$B$}
\rput(3.8,5.2){$C$}
\rput(5.8,5.2){$D$}

\rput(1,0.5){$f$}
\rput(3,0.5){$g$}
\rput(5,0.5){$h$}


\psellipse(0,3)(0.5,2)
\psellipse(2,3)(0.5,2)
\psellipse(4,2.5)(0.5,2.5)
\psellipse(6,3)(0.5,2)

\ncline{->}{a}{2}
\ncline{->}{b}{1}
\ncline{->}{c}{2}
\ncline{->}{2}{x}
\ncline{->}{1}{y}
\ncline{->}{3}{w}
\ncline{->}{x}{4}
\ncline{->}{z}{4}
\ncline{->}{y}{6}
\ncline{->}{w}{5}
   }
 \endpspicture
\end{center}

$f$ est-elle ni injective ni surjective?

\end{multicols}

%doublon
%Q. 59. $(\mathds{N},|)$ est un ensemble ordonné.
%L'assertion proposée est vraie ou fausse ?
Q.59. Si $f:E \longrightarrow F$ est bijective, alors tout élément de $E$ possède exactement une image dans $F$.
L'assertion proposée est vraie ou fausse ?

%doublon
%Q. 60. $x \mathcal{R} y \Longleftrightarrow $ \og $x$ et $y$ ont le même reste dans une division par 2 \fg{} est une relation d'ordre sur les entiers strictement positifs.
%L'assertion proposée est vraie ou fausse ?

Q. 60. Une application injective est une application telle que tout élément de l'ensemble d'arrivée possède exactement un antécédent.
 L'assertion proposée est vraie ou fausse ?

% Q. 62. 

% Q. 63. 

% Q. 65. 
% Etant données les fonctions $f:A \rightarrow B$,
% $g:B \rightarrow C$ et
% $h:C \rightarrow D$ définies par le diagramme suivants

% \begin{center}
% \pspicture*(-1,-1)(7,5.4)
% \scalebox{1}{
% \cnodeput*(0,4){a}{a}
% \cnodeput*(0,3){b}{b}
% \cnodeput*(0,2){c}{c}
% \cnodeput*(2,4){1}{1}
% \cnodeput*(2,3){2}{2}
% \cnodeput*(2,2){3}{3}
% \cnodeput*(4,4){x}{x}
% \cnodeput*(4,3){y}{y}
% \cnodeput*(4,2){z}{z}
% \cnodeput*(4,1){w}{w}
% \cnodeput*(6,4){4}{4}
% \cnodeput*(6,3){5}{5}
% \cnodeput*(6,2){6}{6}

% \rput(-0.2,5.2){$A$}
% \rput(1.8,5.2){$B$}
% \rput(3.8,5.2){$C$}
% \rput(5.8,5.2){$D$}

% \rput(1,0.5){$f$}
% \rput(3,0.5){$g$}
% \rput(5,0.5){$h$}


% \psellipse(0,3)(0.5,2)
% \psellipse(2,3)(0.5,2)
% \psellipse(4,2.5)(0.5,2.5)
% \psellipse(6,3)(0.5,2)

% \ncline{->}{a}{2}
% \ncline{->}{b}{1}
% \ncline{->}{c}{2}
% \ncline{->}{2}{x}
% \ncline{->}{1}{y}
% \ncline{->}{3}{w}
% \ncline{->}{x}{4}
% \ncline{->}{z}{4}
% \ncline{->}{y}{6}
% \ncline{->}{w}{5}
%    }
%  \endpspicture
% \end{center}

% $h \circ g$ est-elle surjective?

% Q. 66. Si $f:E \longrightarrow F$ est bijective, alors tout élément de $F$ possède exactement un antécédant dans $E$. L'assertion proposée est vraie ou fausse ?

% Q. 67. Soit $\mathcal{R}$ une relation binaire définie sur un ensemble $E$, de graphe $G$. $\mathcal{R}$ est dite réflexive quand tout élément est en relation avec lui-même. L'assertion proposée est vraie ou fausse ?

% Q. 68. Soit $\mathcal{R}$ une relation binaire. Il est possible d'avoir $x \mathcal{R} y$ sans avoir $y \mathcal{R} x$. L'assertion proposée est vraie ou fausse ?

% Q. 69. 
% 
%
% %Q. 72. $\mathds{Q}$ a la puissance du continu.
% %L'assertion proposée est vraie ou fausse ?\\ 
% Q. 72. 


\begin{large}
\begin{center}
\begin{tabular}{|l|c|c||l|c|c||l|c|c|}
\hline
Numéro & V & F & Numéro & V & F & Numéro & V & F \\ 
\hline
Q. 1 & &  & Q. 2 & &  & Q. 3 & &  \\ 
\hline
Q. 4 & &  & Q. 5 & &  & Q. 6 & &  \\ 
\hline
Q. 7 & &  & Q. 8 & &  & Q. 9 & &  \\ 
\hline
Q. 10 & &  & Q. 11 & &  & Q. 12 & &  \\ 
\hline
Q. 13 & &  & Q. 14 & &  & Q. 15 & &  \\ 
\hline
Q. 16 & &  & Q. 17 & &  & Q. 18 & &  \\ 
\hline
Q. 19 & &  & Q. 20 & &  & Q. 21 & &  \\ 
\hline
Q. 22 & &  & Q. 23 & &  & Q. 24 & &  \\ 
\hline
Q. 25 & &  & Q. 26 & &  & Q. 27 & &  \\ 
\hline
Q. 28 & &  & Q. 29 & &  & Q. 30 & &  \\ 
\hline
Q. 31 & &  & Q. 32 & &  & Q. 33 & &  \\ 
\hline
Q. 34 & &  & Q. 35 & &  & Q. 36 & &  \\ 
\hline
Q. 37 & &  & Q. 38 & &  & Q. 39 & &  \\ 
\hline
Q. 40 & &  & Q. 41 & &  & Q. 42 & &  \\ 
\hline
Q. 43 & &  & Q. 44 & &  & Q. 45 & &  \\ 
\hline
Q. 46 & &  & Q. 47 & &  & Q. 48 & &  \\ 
\hline
Q. 49 & &  & Q. 50 & &  & Q. 51 & &  \\ 
\hline
Q. 52 & &  & Q. 53 & &  & Q. 54 & &  \\ 
\hline
Q. 55 & &  & Q. 56 & &  & Q. 57 & &  \\ 
\hline
Q. 58 & &  & Q. 59 & &  & Q. 60 & &  \\ 
\hline
\end{tabular}
\end{center}
\end{large}

\newpage
\section{Problèmes}

Vous traiterez au choix deux des trois problèmes suivants.

\subsection{Une relation d'ordre en algèbre de Boole}
Dans une algèbre de Boole munie des opérateurs classiques +, . 
et $\overline{\begin{array}{l}~\end{array}}$
soit la relation $R$ définie par 
$$ x R y \Leftrightarrow x +y = y $$

\begin{enumerate}
\item A-t-on 
  $a\overline{c}d ~R~ ad$, 
  $ad ~R~ a\overline{c}d$, 
  $a\overline{c}d ~R~ \overline{a}\overline{b}cd$ ? Justifier à chaque fois.
\item Montrer que $R$ est une relation d'ordre 
  (réflexive, antisymétrique et transitive).
\item La relation est-elle totale? Partielle? Justifier.
\end{enumerate}

\subsection{Résolution d'équations en  algèbre de Boole}

On considère une boite noire qui réalise l'addition de deux bits 
$a$ et $b$ plus une retenu entrante $c_{\textit{in}}$.   
Elle produit un résultat $s$ et un bit de retenu $c_{\textit{out}}$ en 
se conformant au tableau suivant:
$$
 \begin{array}{|c|c|c|c|c|}
   \hline
   a &b & c_{\textit{in}} & c_{\textit{out}} & s \\
   \hline
   0 &0 & 0 &0 & 0 \\
   \hline
   0 &0 & 1 &0 & 1 \\
   \hline
   0 &1 & 0 &0 & 1 \\
   \hline
   0 &1 & 1 &1 & 0 \\
   \hline
   1 &0 & 0 &0 & 1 \\
   \hline
   1 &0 & 1 &1 & 0 \\
   \hline
   1 &1 & 0 &1 & 0 \\
   \hline
   1 &1 & 0 &1 & 1 \\
   \hline
 \end{array}
$$ 
\begin{enumerate}
\item Montrer que la sortie $s$ est 
  $c_{\textit{in}}(\overline{a}.\overline{b} + a.b) + 
  \overline{c_{\textit{in}}}(\overline{a}.b + a.\overline{b})$
\item Montrer que la retenue $c_{\textit{out}}$ de sortie est 
  $a.b + c_{\textit{in}}.a + c_{\textit{in}}.b$
\item Résoudre algébriquement l'équation $s = c_{\textit{out}}$ dont les 
  variables sont $c_{\textit{in}}$, $a$ et $b$.
  Vérifier la correction des réponses à l'aide du tableau donné ci-dessus.
\end{enumerate}

\subsection{Les infinis}
\begin{enumerate}
\item Parmi les ensembles suivants, $\mathbb{N}, \mathbb{Z}, \mathbb{D}, \mathbb{Q}, \mathbb{R}, \mathbb{C}$, lesquels sont 
dénombrables? Justifier.


\item L'ensemble des nombres transcendants est-il dénombrable? Justifier.

\item Quelle est la définition d'un ensemble infini?

\item Combien y a-t-il d'infinis? Justifier.

\item Démontrez que l'intervalle réel [0,1] n'est pas dénombrable.
\end{enumerate}

\end{document}
